package com.jack.leetcode.每日一题;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树的序列化与反序列化 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "X,";
        }
        String leftSerialize = serialize(root.left);
        String rightSerialize = serialize(root.right);
        return root.val + "," + leftSerialize + rightSerialize;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        Queue<String> queue = new LinkedList<>();
        for (String s : split) {
            queue.add(s);
        }
        return buildTree(queue);
    }

    private TreeNode buildTree(Queue<String> queue){
        String s = queue.poll();
        if("X".equalsIgnoreCase(s)){
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(s));
        node.left = buildTree(queue);
        node.right = buildTree(queue);
        return node;
    }
}
